Programación Avanzada

1 Contenido de la clase

Algoritmo: definición y características

Un algoritmo es un método de solución para resolver un problema. Sus características (según el material de la clase):

• Para encontrar la solución puede requerir información (datos).
• Al seguir el método se genera al menos un resultado.
• Está definido mediante un conjunto finito de pasos (finitud).
• Cada paso es susceptible de ser realizado por cualquier persona con papel y lápiz (definición).
• El seguir (ejecutar) el algoritmo lleva un tiempo finito (terminación).

También se da una definición breve: un algoritmo es un conjunto de pasos para resolver un problema.

Lenguaje de programación

Un lenguaje de programación es un lenguaje que permite expresar un algoritmo de modo que pueda ejecutarse en una computadora: es un lenguaje que permite expresar un algoritmo en un lenguaje que pueda entender una computadora.

Definición formal: gramática y lenguaje L(G)

Una gramática G es una 4-tupla (V, S, Vo, →) donde:

• V: conjunto finito de símbolos.
• S: subconjunto de V; son las palabras permitidas del lenguaje (tokens o palabras reservadas).
• Vo: símbolo inicial de las reglas de producción (Vo ∈ V − S).
• →: relación finita sobre V*; son las reglas de producción o sustitución.

Se definen además N = V − S (símbolos no terminales) y V = S ∪ N. Dada una gramática G, el lenguaje L(G) es el conjunto de símbolos terminales que genera la gramática: los que se obtienen a partir del símbolo inicial aplicando las reglas de producción o sustitución.

Jerarquía de Chomsky

Según el tipo de restricciones en las reglas de producción, las gramáticas se clasifican (Noam Chomsky):

• Tipo 0: no existe ninguna restricción.
• Tipo 1: w1 → w2 donde la longitud de w1 ≤ la longitud de w2; se les conoce como sensibles al contexto. Junto con las de tipo 0 son difíciles y poco estudiadas.
• Tipo 2: w1 → w2 donde w1 tiene un solo símbolo no terminal y w2 tiene uno o más símbolos; son las gramáticas libres de contexto.
• Tipo 3: w1 → w2 donde w1 tiene un solo símbolo no terminal y w2 tiene a lo más un símbolo no terminal a la extrema derecha; son las gramáticas regulares.

La mayoría de los lenguajes de programación son generados por una gramática de tipo 2.

Clasificación de los lenguajes de programación

• Por nivel: de alto nivel (según su propósito o paradigma) y de bajo nivel (ensamblador y de máquina).
• Por paradigma: POO, concurrentes, paralelos, funcionales, lógicos y visuales.
• Declarativos — responden a ¿qué hay que hacer?: funcionales (Lisp, Haskell, Miranda, Scheme, ML) y lógicos (Prolog).
• Imperativos (procedurales) — responden a ¿cómo hacerlo?: Fortran, Cobol, C, Basic, Java, Pascal, C++.
• Por su manera de ejecutarse: compilados e interpretados.

Programa, programación y la frase de Wirth

Un programa es un algoritmo escrito en un lenguaje de programación de alto nivel, llamado código fuente; formalmente, es un conjunto de símbolos terminales de una gramática G que se obtiene a partir del símbolo inicial aplicando correctamente las reglas de producción (es decir, sintácticamente correcto). La programación es escribir y diseñar programas: escribir, diseñar, analizar y plantear algoritmos en un lenguaje de programación.

Frase de Niklaus Emil Wirth (1975): Algorithms + Data Structures = Programs.

Técnicas de programación (años 60)

Las técnicas de programación son el conjunto de métodos y modelos que permiten escribir algoritmos eficientes en un lenguaje para resolver un problema. Surgieron en los años 60:

• Programación estructurada.
• Diseño modular.
• Diseño descendente (arriba a abajo, top-down).

Aquí aparece la cohesión: medida de la definición de un módulo; establece si un módulo tiene una función bien definida dentro del sistema.

Teorema de la programación estructurada (Böhm-Jacopini)

El teorema de Corrado Böhm y Giuseppe Jacopini (1966) establece que todo algoritmo puede ser implementado en un lenguaje que combine solo tres estructuras lógicas de control:

• Secuencia: ejecución de una instrucción tras otra.
• Selección: ejecución de una de dos instrucciones (o grupo) según el valor de una variable booleana (condición).
• Iteración: ejecución de una instrucción (o grupo) mientras una variable booleana sea verdadera (mientras una condición se cumpla).

Programación modular: cohesión y acoplamiento

La programación modular agrupa instrucciones bajo un nombre que realizan una tarea específica. Características: los módulos son independientes, guardan una relación lógica, se pueden probar de manera independiente, se comunican entre sí por medio de parámetros y pueden regresar un valor (funciones) o varios a través de los parámetros.

• Alta cohesión: hace más fácil entender qué hace un módulo, clase o método; usar nombres descriptivos; reutilizar clases o métodos; y la programación y el mantenimiento.
• Acoplamiento: medida de la dependencia entre módulos, clases o métodos. Un bajo acoplamiento permite entender una clase sin leer otras, cambiar una clase sin afectar a otras y mejora el mantenimiento.

En la práctica se desea lograr a la vez alta cohesión y bajo acoplamiento; el material advierte que por el tamaño y la complejidad de las aplicaciones actuales estas técnicas ya no son suficientes, y menciona que Spring es un framework que promueve una alta cohesión y un bajo acoplamiento entre sus componentes.

Técnicas modernas: abstracción, POO, POA y arquitectura de software

Las técnicas modernas incluyen la abstracción, la POO (con clases, herencia y encapsulación), la POA (programación orientada a aspectos) y la arquitectura de software: la descripción del conjunto de elementos requeridos para construir un sistema de software; define las relaciones entre ellos y las propiedades de cada uno (la estructura de un sistema). Se cita la norma ISO/IEC/IEEE 42010:2011: conjunto de conceptos y propiedades fundamentales de un sistema en su entorno, plasmadas en sus elementos, relaciones y en los principios de su diseño y evolución.

Patrones de diseño

Definición de Christopher Alexander: "cada patrón describe un problema que ocurre una y otra vez en nuestro entorno y describe también el núcleo de la solución al problema, de forma que puede utilizarse un millón de veces sin tener que hacer dos veces lo mismo". Se clasifican en de creación, de comportamiento, estructurales, de sistema y de concurrencia.

• Patrones de creación: tratan las formas de crear instancias de objetos; su objetivo es abstraer el proceso de instanciación y ocultar cómo se crean o inicializan. Ejemplos: Abstract Factory (Fábrica Abstracta), Builder (Constructor), Factory Method (Método de Fabricación), Prototype (Prototipo), Singleton (Único).
• Patrones de sistema o de arquitectura: establecen cómo organizar y comunicar los componentes de un sistema. Ejemplos: Model View Controller (MVC), Session (Sesión), Worker Thread (Hilo trabajador), Callback (Retrollamada), Successive Update (Actualización Sucesiva), Router (Encaminador), Transaction (Transacción).

Arquitectura de aplicaciones web (MVC) y cierre

La lámina cierra con la arquitectura de aplicaciones web y el modelo-vista-controlador (MVC), y remite a ver un ejemplo de aplicación empresarial web en Eclipse y a los Core J2EE Patterns (java.sun.com/blueprints/corej2eepatterns/Patterns). Esta clase sienta las definiciones que enlazan con las técnicas de solución de problemas y la demostración formal de programas de las clases siguientes.

2 Puntos destacados / Lo que hay que saber

3 Actividades y tareas pendientes

No se dejó en esta clase una tarea con fecha de entrega.

4 Dudas que podrían examinar

5 Sitios o recursos para visitar

• ISO/IEC/IEEE 42010:2011 — norma de arquitectura de software citada en la lámina (dominio: google.com).
• Niklaus Wirth · Algorithms + Data Structures = Programs (1975) — frase/fundamento de la clase sobre algoritmos y estructuras de datos (dominio: google.com).
• Teorema de Böhm-Jacopini (1966) — base de la programación estructurada (dominio: google.com).
• Spring framework — framework mencionado en clase como ejemplo de alta cohesión y bajo acoplamiento (dominio: spring.io).
• Patrones de diseño (GoF) — catálogo clásico de patrones de creación, comportamiento y estructurales (dominio: google.com).
• Core J2EE Patterns (Java BluePrints) — catálogo de patrones de arquitectura citado en la lámina (dominio: google.com).

6 Glosario de términos

• Algoritmo: método de solución de un problema con pasos finitos y definidos, que termina en tiempo finito
• Lenguaje de programación: lenguaje que permite expresar un algoritmo para que lo entienda y ejecute una computadora
• Gramática G: 4-tupla (V, S, Vo, →) que define formalmente un lenguaje
• Tokens / palabras reservadas: las palabras permitidas de un lenguaje (elementos de S)
• Reglas de producción o sustitución (→): relación finita sobre V* que genera las cadenas del lenguaje
• Símbolos terminales y no terminales: palabras permitidas (S) frente a símbolos que se reescriben (N = V − S)
• L(G): lenguaje generado por una gramática: símbolos terminales obtenidos desde el símbolo inicial aplicando las reglas
• Jerarquía de Chomsky: clasificación de gramáticas en tipos 0, 1 (sensibles al contexto), 2 (libres de contexto) y 3 (regulares)
• Lenguaje de alto/bajo nivel: cercano al problema (alto) frente a cercano a la máquina (ensamblador y máquina)
• Paradigma declarativo: expresa qué hay que hacer (funcional y lógico)
• Paradigma imperativo (procedural): expresa cómo hacerlo, paso a paso
• Programa: algoritmo expresado como código fuente sintácticamente correcto en un lenguaje
• Código fuente: algoritmo escrito en un lenguaje de programación de alto nivel
• Programación: escribir, diseñar, analizar y plantear algoritmos en un lenguaje de programación
• Programación estructurada: técnica basada en secuencia, selección e iteración (Böhm-Jacopini, 1966)
• Diseño modular: agrupar instrucciones bajo un nombre para realizar una tarea específica
• Diseño descendente (top-down): resolver de arriba hacia abajo, descomponiendo el problema
• Cohesión: medida de si un módulo tiene una función bien definida; se desea alta
• Acoplamiento: medida de la dependencia entre módulos, clases o métodos; se desea bajo
• Arquitectura de software: estructura de un sistema: elementos, relaciones y propiedades (ISO/IEC/IEEE 42010:2011)
• Patrón de diseño: solución reutilizable a un problema recurrente (definición de Christopher Alexander)
• Patrones de creación: abstraen el proceso de instanciación (Abstract Factory, Builder, Factory Method, Prototype, Singleton)
• Patrones de sistema: organizan y comunican los componentes (MVC, Session, Worker Thread, Callback, Successive Update, Router, Transaction)
• MVC: Modelo-Vista-Controlador: patrón de arquitectura de aplicaciones web que separa modelo, vista y controlador

7 Mapa mental textual

• Programación Avanzada · Clase 1 — Definiciones básicas: algoritmo, gramáticas y técnicas de programación
  • Algoritmo y lenguaje
    • Algoritmo: finitud · definición (papel y lápiz) · terminación · datos · resultado
    • Lenguaje de programación: expresar algoritmos para la computadora
    • Programa (código fuente) · Programación · Wirth 1975 (Algorithms + Data Structures = Programs)
  • Definición formal: gramáticas
    • G = (V, S, Vo, →) · terminales/no terminales · reglas de producción · L(G)
    • Jerarquía de Chomsky: tipos 0 · 1 (sensible al contexto) · 2 (libre de contexto) · 3 (regular)
    • Lenguajes de programación → gramáticas tipo 2
  • Clasificación de lenguajes
    • Nivel: alto / bajo (ensamblador, máquina)
    • Paradigma: declarativos (funcionales/lógicos) vs imperativos; POO, concurrentes, paralelos, visuales
    • Ejecución: compilados / interpretados
  • Técnicas de programación (años 60)
    • Estructurada · Modular · Descendente (top-down)
    • Teorema de Böhm-Jacopini: secuencia · selección · iteración
    • Cohesión (alta) y acoplamiento (bajo) · Spring
  • Técnicas modernas
    • Abstracción · POO (clases, herencia, encapsulación) · POA
    • Arquitectura de software (ISO/IEC/IEEE 42010:2011)
    • Patrones de diseño (Christopher Alexander): creación · comportamiento · estructurales · sistema · concurrencia
  • Arquitectura de aplicaciones web
    • MVC y ejemplo en Eclipse
    • Core J2EE Patterns